package com.company.ljh.utils;

/**
 * @description:
 * 优先级队列（堆）
 * @projectName:leet_code
 * @see:com.company.ljh.utils
 * @author:ljh
 * @createTime:2023/7/7 11:53
 * @version:1.0
 */
public class PriorityQueue {
    int [] data;
    int heapSize = 0;

    //大根堆 PriorityQueue，一般使用数组实现
    //需要保存heapSize，即当前二叉树节点数量
    //构建时直接添加到最后一个节点，然后进行调整

    public void buildMaxHeap(int nums[],int heapSize){
        data = nums;
        //从最后一个非叶子节点开始进行调整
        for(int i = (heapSize - 2) /2;i >= 0;i--){
            //递归调整
            maxHeapify(data,i,heapSize);
        }

    }
    
    private void maxHeapify(int[] nums, int i, int heapSize) {
        int left = i*2 + 1;
        int right = i*2 + 2;
        //用于保存数据最大的指针
        int max = i;
        if(left < heapSize && nums[left] > nums[max]){
            //左子节点最大
            max = left;
        }
        if(right < heapSize && nums[right] > nums[max]){
            //右子节点最大
            max = right;
        }
        if(max != i){
            swap(nums,i,max);
            maxHeapify(nums,max,heapSize);
        }
    }

    private void swap(int[] nums, int i, int max) {
        int temp = nums[i];
        nums[i] = nums[max];
        nums[max] = temp;
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        int [] nums = new int []{3,2,3,1,2,4,5,5,6};
        priorityQueue.buildMaxHeap(nums,9);
        System.out.println(nums);
    }
}
